package com.test.gpa.test.suanfa;

import java.util.*;

public class Solo {
    public int maxPathSum(TreeNode root) {
        dfs(root);
        return max;
    }

    int max = Integer.MIN_VALUE;

    int dfs(TreeNode treeNode) {
        if (treeNode == null) return 0;
        int left = Math.max(dfs(treeNode.left), 0);
        int right = Math.max(dfs(treeNode.right), 0);
        int max1 = Math.max(left, right);
        max = Math.max(left + right + treeNode.val, max);
        return max1 + treeNode.val;
    }


    public TreeNode increasingBST(TreeNode root) {
        if (root == null) return null;

        dfs1(root);
        TreeNode treeNode = new TreeNode(queue.poll());
        root = treeNode;
        while (!queue.isEmpty()) {
            treeNode.right = new TreeNode(queue.poll());
            treeNode = treeNode.right;
        }
        return root;
    }

    Queue<Integer> queue = new LinkedList<>();

    void dfs1(TreeNode treeNode) {
        if (treeNode == null) return;
        dfs1(treeNode.left);
        queue.add(treeNode.val);
        dfs1(treeNode.right);
    }

    public List<List<Integer>> threeSum(int[] nums) {
        Arrays.sort(nums);
        Set<List<Integer>> list = new HashSet<>();
        for (int i = 0; i < nums.length; i++) {
            int j = i + 1;
            int k = nums.length - 1;
            while (j < k) {
                int sum = nums[i] + nums[j] + nums[k];
                if (sum == 0) {
                    List<Integer> list1 = new ArrayList<>();
                    list1.add(nums[i]);
                    list1.add(nums[j]);
                    list1.add(nums[k]);
                    list.add(list1);
                    j++;
                } else if (sum > 0) {
                    k--;
                } else j++;
            }
        }
        List<List<Integer>> list1 = new ArrayList<>();
        for (List<Integer> list2 :
                list) {
            list1.add(list2);
        }
        return list1;
    }


    public TreeNode inorderSuccessor(TreeNode root, TreeNode p) {
        if (root == null) return null;
        int a = 1;
        while (!deque.isEmpty()) {
            TreeNode poll = deque.poll();
            if (a == 0) return poll;
            if (poll == p) a = 1;
        }
        return null;
    }

    Deque<TreeNode> deque = new LinkedList<>();

    void dfs2(TreeNode treeNode) {
        if (treeNode == null) return;
        dfs2(treeNode.left);
        deque.add(treeNode);
        dfs2(treeNode.right);
    }

    class BSTIterator {
        TreeNode root;
        Deque<TreeNode> deque = new LinkedList<>();

        public BSTIterator(TreeNode root) {
            this.root = root;
            Bst(root);
        }

        public int next() {
            return deque.poll().val;
        }

        public boolean hasNext() {
            return !deque.isEmpty();
        }

        void Bst(TreeNode root) {
            if (root == null) return;
            Bst(root.left);
            deque.add(root);
            Bst(root.right);
        }


    }


    public boolean findTarget(TreeNode root, int k) {
        this.k = k;
        dfs8(root);
        int n = list.size() - 1;

        return we;
    }

    int k = 0;
    List<Integer> list = new LinkedList<>();
    boolean we = false;

    void dfs8(TreeNode treeNode) {
        if (treeNode == null) return;
        int local = treeNode.val;
        dfs8(treeNode.left);
        list.add(local);
        dfs8(treeNode.right);
    }

    public boolean containsNearbyAlmostDuplicate(int[] nums, int k, int t) {
        if (nums.length < 2) return false;
        for (int i = 0; i < nums.length; i++) {
            for (int j = i; j < nums.length; j++) {
                if (Math.abs(nums[i] - nums[j]) < t && Math.abs(i - j) < k) return true;
            }
        }

        return false;
    }

    class MyCalendar1 {

        List<int[]> list;

        public MyCalendar1() {
            list = new ArrayList<>();
        }

        public boolean book(int start, int end) {
            for (int[] a :
                    list) {
                int sta = a[0];
                int en = a[1];
                if (start < en && end > sta) {
                    return false;
                }
            }
            list.add(new int[]{start, end});
            return true;
        }
    }

    class MyCalendar {

        TreeSet<B> booked;

        public MyCalendar() {
            booked = new TreeSet<>();

        }

        public boolean book(int start, int end) {
            return booked.add(new B(start, end));
        }

        class B implements Comparator<B> {
            public B(int start, int end) {
                this.start = start;
                this.end = end;
            }

            int start;
            int end;


            @Override
            public int compare(B o1, B o2) {
                if (o1 instanceof B && o2 instanceof B) {
                    if (((B) o2).start > ((B) o1).end && ((B) o2).end < ((B) o1).start) {
                        return -1;
                    } else return 1;
                }
                return 0;
            }
        }

    }

    class KthLargest {
        PriorityQueue<Integer> queue;
        int k;

        public KthLargest(int k, int[] nums) {
            this.k = k;
            queue = new PriorityQueue<>();
            for (int a :
                    nums) {
                add(a);
            }


        }

        public int add(int val) {
            queue.offer(val);
            if (queue.size() > k) {
                queue.poll();
            }
            return queue.peek();
        }
    }

    public int[] topKFrequent(int[] nums, int k) {
        Map<Integer, Integer> map = new HashMap<>();
        for (int i = 0; i < nums.length; i++) {
            map.put(nums[i], map.getOrDefault(nums[i], 0) + 1);
        }
        PriorityQueue<int[]> queue1 = new PriorityQueue<>(Comparator.comparingInt(x -> x[1]));
        map.forEach((x, y) -> {
            queue1.add(new int[]{x, y});
            if (queue1.size() > k) {
                queue1.poll();
            }

        });
        int[] ints = new int[k];
        int i = 0;
        for (int j = k - 1; j >= 0; j--) {
            ints[j] = queue1.poll()[0];
        }
        return ints;
    }

    public List<List<Integer>> kSmallestPairs(int[] nums1, int[] nums2, int k) {
        PriorityQueue<int[]> queue1 = new PriorityQueue<>((o1, o2) -> o2[0] + o2[1] - o1[0] - o1[1]
        );
        for (int i = 0; i < nums1.length && i <= k; i++) {
            for (int j = 0; j < nums2.length && i <= k; j++) {
                int[] ints = new int[2];
                ints[0] = nums1[i];
                ints[1] = nums2[j];
                queue1.add(ints);
                if (queue1.size() > k) queue1.poll();
            }
        }
        List<List<Integer>> list1 = new ArrayList<>(queue1.size());
        for (int i = 0; i < queue1.size(); i++) {
            list1.add(new ArrayList<>());
        }
        for (int i = queue1.size() - 1; i >= 0; i--) {
            List<Integer> list2 = new LinkedList<>();
            int[] ints = queue1.poll();
            list2.add(ints[0]);
            list2.add(ints[1]);
            list1.set(i, list2);
        }
        return list1;
    }

    class Trie {
        Trie[] children;
        boolean isEnd = false;

        public Trie() {
            children = new Trie[26];
        }

        public void insert(String word) {
            Trie trie = this;
            for (int i = 0; i < word.length(); i++) {
                char lin = word.charAt(i);
                if (trie.children[lin - 'a'] == null) {
                    trie.children[lin - 'a'] = new Trie();
                }
                trie = trie.children[lin - 'a'];
            }
            trie.isEnd = true;
        }

        public boolean search(String word) {
            Trie trie = this;
            for (int i = 0; i < word.length(); i++) {
                char lin = word.charAt(i);
                if (trie.children[lin - 'a'] == null) {
                    return false;
                } else trie = trie.children[lin - 'a'];
            }
            return trie.isEnd;
        }

        public boolean startsWith(String prefix) {
            Trie trie = this;
            for (int i = 0; i < prefix.length(); i++) {
                char lin = prefix.charAt(i);
                if (trie.children[lin - 'a'] == null) {
                    return false;
                } else trie = trie.children[lin - 'a'];
            }
            return true;
        }

    }

    public String replaceWords(List<String> dictionary, String sentence) {
        Trie trie = new Trie();
        for (String s :
                dictionary) {
            trie.insert(s);
        }
        String[] s = sentence.split(" ");
        StringBuilder stringBuilder = new StringBuilder();
        for (int i = 0; i < s.length; i++) {
            for (int j = 1; j < s[i].length(); j++) {
                boolean b = trie.search(s[i].substring(0, j));
                if (b) {
                    s[i] = s[i].substring(0, j);
                    break;
                }
            }
            stringBuilder.append(s[i] + " ");
        }

        return stringBuilder.deleteCharAt(stringBuilder.length() - 1).toString();
    }


    class Tris {
        Map<Character, Tris> map;
        boolean isEnd = false;

        Tris() {
            map = new HashMap<>();
        }

        private void insert(String word) {
            Tris tris = this;
            for (int i = 0; i < word.length(); i++) {
                char c = word.charAt(i);
                if (!tris.map.containsKey(c)) {
                    tris.map.put(c, new Tris());
                }
                tris = tris.map.get(c);
            }
            tris.isEnd = true;
        }

        private boolean search(String str) {
            Tris tris = this;
            for (int i = 0; i < str.length(); i++) {
                char c = str.charAt(i);
                if (!tris.map.containsKey(c)) {
                    return false;
                }
                tris = tris.map.get(c);
            }
            return tris.isEnd;
        }
    }

    public String replaceWords1(List<String> dictionary, String sentence) {

        Tris trie = new Tris();
        for (String s :
                dictionary) {
            trie.insert(s);
        }
        String[] s = sentence.split(" ");
        StringBuilder stringBuilder = new StringBuilder();
        for (int i = 0; i < s.length; i++) {
            for (int j = 1; j < s[i].length(); j++) {
                boolean b = trie.search(s[i].substring(0, j));
                if (b) {
                    s[i] = s[i].substring(0, j);
                    break;
                }
            }
            stringBuilder.append(s[i] + " ");
        }
        return stringBuilder.deleteCharAt(stringBuilder.length() - 1).toString();
    }


    public String smallestNumber(String pattern) {
        int[] ints = new int[]{0, 1, 2, 3, 4, 5, 6, 7, 8, 9};
        for (int i = 1; i < 10; i++) {
            ints[i] = 0;
            dfs(new StringBuilder().append(i), pattern, pattern.length() + 1, ints);
            ints[i] = i;
        }
        Long ans = Long.MAX_VALUE;
        for (String sum :
                longTreeSet) {
            ans = Math.min(ans, Long.valueOf(sum));
        }
        return String.valueOf(ans);
    }

    Set<String> longTreeSet = new TreeSet<>();

    void dfs(StringBuilder ans, String pattern, int len, int[] ints) {
        int length = ans.length();
        if (length == len) {
            longTreeSet.add(String.valueOf(ans));
            return;
        }
        if (pattern.charAt(length - 1) == 'D') {
            for (int i = ans.charAt(length - 1) - '0'; i >= 0; i--) {
                if (ints[i] != 0 && ints[i] + '0' < ans.charAt(length - 1)) {
                    newDfs(ans, pattern, len, ints, i);
                    return;
                }
            }
        } else if (pattern.charAt(length - 1) == 'I') {
            for (int i = ans.charAt(length - 1) - '0'; i < len; i++) {
                if (ints[i] != 0 && ints[i] + '0' > ans.charAt(length - 1)) {
                    newDfs(ans, pattern, len, ints, i);
                    return;
                }
            }
        }
    }

    private void newDfs(StringBuilder ans, String pattern, int len, int[] ints, int i) {
        StringBuilder stringBuilder = new StringBuilder(ans.append(ints[i]).toString());
        ints[i] = 0;
        dfs(stringBuilder, pattern, len, Arrays.copyOf(ints, ints.length));
        ints[i] = i;
        ans.deleteCharAt(ans.length() - 1);
    }

    class MagicDictionary {
        List<String> strings;

        /**
         * Initialize your data structure here.
         */
        public MagicDictionary() {
            strings = new LinkedList<>();
        }

        public void buildDict(String[] dictionary) {
            for (String s :
                    dictionary) {
                strings.add(s);
            }
        }

        public boolean search(String searchWord) {
            boolean ans = false;
            for (String s :
                    strings) {
                int isBlank = 0;
                for (int j = 0; j < searchWord.length(); j++) {
                    if (searchWord.length() != s.length()) break;
                    if (searchWord.charAt(j) != s.charAt(j)) {
                        isBlank++;
                    }
                }
                if (isBlank == 1) {
                    ans = true;
                }
            }
            return ans;
        }
    }


    class Prefix {
        Map<Character, Prefix> map;
        boolean isEnd = false;

        public Prefix() {
            map = new HashMap();
        }

        public void insert(String word) {
            Prefix prefix = this;
            for (int i = 0; i < word.length(); i++) {
                char c = word.charAt(i);
                if (prefix.map.get(c) == null) {
                    prefix.map.put(c, new Prefix());
                }
                prefix = prefix.map.get(c);
            }
            prefix.isEnd = true;
        }

        int count = 0;

        public void countNode(Prefix root, Prefix prefix, int sum) {
            if (prefix.map.size() == 0) {
                root.count += sum;
                return;
            }
            for (Character character :
                    prefix.map.keySet()) {
                countNode(root, prefix.map.get(character), sum + 1);
            }
        }

    }

    public int minimumLengthEncoding(String[] words) {
        if (words == null) return 0;
        Prefix prefix = new Prefix();
        for (String str :
                words) {
            StringBuilder stringBuilder = new StringBuilder(str).reverse();
            prefix.insert(stringBuilder.toString());
        }
        prefix.countNode(prefix, prefix, 1);
        return prefix.count;
    }

    public static void main(String[] args) {
        Solo solo = new Solo();
        solo.minimumLengthEncoding(new String[]{"time", "me", "bell"});
    }

    class MapSum {
        class Node {
            Map<Character, Node> map = new HashMap<>();
            int count;

            public void insert(String key, int val) {
                Node node = this;
                for (int i = 0; i < key.length(); i++) {
                    char c = key.charAt(i);
                    if (node.map.get(c) == null) {
                        Node node1 = new Node();
                        node.map.put(c, node1);
                    }
                    node = node.map.get(c);
                }
                node.count = val;
            }
        }

        Node root;

        public MapSum() {
            root = new Node();
        }

        public void insert(String key, int val) {
            root.insert(key, val);
        }

        public int sum(String prefix) {
            Node node1 = this.root;
            for (int i = 0; i < prefix.length(); i++) {
                char c = prefix.charAt(i);
                if (node1.map.get(c) == null) {
                    return 0;
                }
                node1 = node1.map.get(c);
            }
            sum = 0;
            dfs(node1);
            return sum;
        }

        int sum = 0;

        void dfs(Node node) {
            if (node == null) return;
            if (node.count != 0) {
                sum += node.count;
            }
            for (Character k :
                    node.map.keySet()) {
                dfs(node.map.get(k));
            }
        }

    }

    class MapSum1 {
        Map<String, Integer> map;

        public MapSum1() {
            map = new HashMap<>();
        }

        public void insert(String key, int val) {
            map.put(key, val);
        }

        public int sum(String prefix) {
            int count = 0;
            for (String s :
                    map.keySet()) {
                if (s.startsWith(prefix)) {
                    count += map.getOrDefault(s, 0);
                }
            }
            return count;
        }
    }


}
